# class Tree:
#     def __init__(self):
#         self.left = None  # 左叉树
#         self.right = None  # 右叉树
#         self.data = None  # 根节点
#
#
# root = Tree()
# root.data = "中国"
#
# root.left = Tree()
# root.left.data = "山西"
#
# root.right = Tree()
# root.right.data = "北京"
#
# root.left.left = Tree()
# root.left.left.data = "吕梁市"
#
# print(root.left.data)

# 创建二叉树
# class Tree:
#     def __init__(self):
#         self.left = None  # 左叉树
#         self.right = None  # 右叉树
#         self.data = None  # 根节点
#         self.z = []  # 存放到列表中
#
#     # 前序遍历 -- 根->左->右
#     def preorder(self, node):
#         self.z.append(node.data)
#         if node.left != None:
#             self.preorder(node.left)
#         if node.right != None:
#             self.preorder(node.right)
#
#     # 中序遍历 -- 左->根->右
#     def infixorder(self, node):
#         if node.left != None:
#             self.infixorder(node.left)
#         self.z.append(node.data)
#         if node.right != None:
#             self.infixorder(node.right)
#
#     # 后序遍历 -- 左->右->根
#     def epilogue(self, node):
#         if node.left != None:
#             self.epilogue(node.left)
#         if node.right != None:
#             self.epilogue(node.right)
#         self.z.append(node.data)
#
#     # 查找
#     def search(self, node, z, data):
#         if not node.left == None:
#             z = self.search(node.left, z, data)
#         if not node.right == None:
#             z = self.search(node.right, z, data)
#
#         if z != []:
#             # 判断当前节点是否在查询节点的线上
#             if node.left != None:
#                 if z[-1] == node.left.data:
#                     z.append(node.data)
#             if node.right != None:
#                 if z[-1] == node.right.data:
#                     z.append(node.data)
#
#         if node.data == data:
#             z.append(data)
#         return z
#
#
# root = Tree()
# root.data = 0
#
# root.left = Tree()
# root.left.data = 1
#
# root.right = Tree()
# root.right.data = 2
#
# root.left.left = Tree()
# root.left.left.data = 3
#
# root.left.right = Tree()
# root.left.right.data = 4
#
# root.right.left = Tree()
# root.right.left.data = 5
#
# root.right.right = Tree()
# root.right.right.data = 6
#
# print('前序遍历：')
# root.z = []
# root.preorder(root)
# print(root.z)
#
# print('中序遍历：')
# root.z = []
# root.infixorder(root)
# print(root.z)
#
# print('后序遍历：')
# root.z = []
# root.epilogue(root)
# print(root.z)
#
# print(root.search(root, [], 1))


class BSTnode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        newNode = BSTnode(val)
        if self.root is None:
            self.root = newNode
        else:
            curNode = self.root
            while True:
                # 进入左子树
                if val < curNode.val:
                    if curNode.left is None:
                        curNode.left = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.left
                else:
                    # 进入右子树
                    if curNode.right is None:
                        curNode.right = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.right

    def find(self, val):
        curNode = self.root
        while curNode is not None:
            if val < curNode.val:
                curNode = curNode.left
            elif val > curNode.val:
                curNode = curNode.right
            else:
                return True
        return False


mylist = [1, 2, 3, 4, 5]
bst = BST()
for x in range(len(mylist)):
    bst.insert(mylist[x])
print(bst.find(4))
